#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* 将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。
输入格式:

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:

对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

 */

/* 类型定义 */

typedef int ElemType;

/* 堆的类型枚举定义 */
enum _heaptype
{
    MaxHeap,
    MinHeap
};
typedef enum _heaptype HeapType;

/* 堆类型定义 */
struct _HeapStruct
{
    ElemType *elems;   /* 堆中元素指针，0号元素留空 */
    unsigned size;     /* 当前堆大小 */
    unsigned capacity; /* 堆的最大容量 */
    HeapType type;     /* 堆的类型 */
};
typedef struct _HeapStruct HeapStruct;

/* 函数声明 */
int heap_adjust(HeapStruct *heap, unsigned index);
HeapStruct *new_heap(unsigned capacity, HeapType type);
void show_heap(HeapStruct *heap);

int main(int argc, char *argv[])
{
    /* n 插入元素的个数, m 需要打印的路径条数 */
    unsigned n, m;
    m = n = 0;
    FILE *file;

    if (argc > 1)
    {
        file = fopen(argv[1], "r");
        if (!file)
        {
            printf("Fail to open %s\n", argv[1]);
            exit(-1);
        }
    }
    else
        file = stdin;

    fscanf(file, "%u %u", &m, &n);
    /* 新建堆 */
    HeapStruct *heap = new_heap(m, MinHeap);
    /* 输入元素 */
    for (int i = 0; i < m; i++)
        fscanf(file, "%d", heap->elems + (++(heap->size)));

    for (unsigned i = heap->size; i > 1; i /= 2)
    {
        heap_adjust(heap, i / 2);
    }
    show_heap(heap);
}

int heap_adjust(HeapStruct *heap, unsigned index)
{
    /* 函数目的：使当前堆的根比左右孩子小 
       找到子树中较大的，若根较小则交换 */
    unsigned left_son = index * 2;
    unsigned right_son = index * 2 + 1;
    /* min_index, 左右节点中较小的那个 */
    unsigned min_index;
    /* 求出最小的索引 */
    /* left_son超出边界 此节点为叶节点, 无需操作 */
    if (left_son > heap->size)
        return 0;
    /* left_son未超出边界,但right_sonh超出 直接与左节点比较即可 */
    if (right_son > heap->size)
        min_index = left_son;
    /* 左右节点均存在 */
    min_index = heap->elems[left_son] < heap->elems[right_son] ? left_son : right_son;
    /* 与最小的做对比，若比最小的还小，则交换 */

    //TODO 调整算法应改变为比较所有子孙节点
    if (heap->elems[index] > heap->elems[min_index])
    {
        heap->elems[0] = heap->elems[index];
        heap->elems[index] = heap->elems[min_index];
        heap->elems[min_index] = heap->elems[0];
    }
    return 0;
}

HeapStruct *new_heap(unsigned capacity, HeapType type)
{
    HeapStruct *heap = malloc(sizeof(HeapStruct));
    heap->elems = malloc(sizeof(ElemType) * (capacity + 1));
    heap->size = 0;
    heap->capacity = capacity;
    heap->type = type;

    memset(heap->elems, 0, (capacity + 1) * sizeof(ElemType));
    return heap;
}

void heap_path(HeapStruct* heap,unsigned i){
    
}

void show_heap(HeapStruct *heap)
{
    if (!heap)
        return;
    printf("heap type:%s size: %u/%u\n", heap->type == MinHeap ? "MinHeap" : "MaxHeap", heap->size, heap->capacity);
    printf("heap->elems[0] = %d \n", heap->elems[0]);
    for (unsigned i = 1; i < heap->size + 1; i++)
    {
        printf("%d ", heap->elems[i]);
    }
    putchar('\n');
}